#include <iostream>
using namespace std;

struct TreeNode {
  int val;
  TreeNode *left;
  TreeNode *right;
  TreeNode() : val(0), left(nullptr), right(nullptr) {}
  TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
  TreeNode(int x, TreeNode *left, TreeNode *right)
      : val(x), left(left), right(right) {}
};
class Solution {
  bool isEq(TreeNode *root, TreeNode *sub) {
    if ((root == nullptr) && (sub != nullptr)) {
      return false;
    }

    if ((root != nullptr) && (sub == nullptr)) {
      return false;
    }

    if ((root == nullptr) && (sub == nullptr)) {
      return true;
    }

    if (root->val != sub->val) {
      return false;
    }
    return isEq(root->left, sub->left) && isEq(root->right, sub->right);
  }

public:
  bool isSubtree(TreeNode *root, TreeNode *subRoot) {
    if ((root == nullptr) && (subRoot != nullptr)) {
      return false;
    }
    if ((root != nullptr) && (subRoot == nullptr)) {
      return false;
    }

    if (isEq(root, subRoot)) {
      return true;
    }
    return isSubtree(root->left, subRoot) || isSubtree(root->right, subRoot);
  }
};

int main(int argc, char *argv[]) {
  TreeNode a;
  a.val = 4;
  TreeNode b;
  b.val = 1;
  TreeNode c;
  c.val = 2;
  TreeNode d;
  c.val = 0;

  a.left = &b;
  a.right = &c;
  c.left = &d;

  TreeNode e;
  e.val = 4;
  TreeNode f;
  f.val = 1;
  TreeNode g;
  g.val = 2;
  e.left = &f;
  e.right = &g;

  Solution s;
  s.isSubtree(&a, &e);

  return 0;
}
